package pers.qianyu.month_202101.date_20210113;

/**
 * @author mizzle rain
 * @date 2021-01-13 21:49
 */
public class WordSearch {
    int[][] dxy = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    int h, w;
    char[][] board;
    String word;

    public boolean exist(char[][] board, String word) {
        h = board.length;
        w = board[0].length;
        this.board = board;
        this.word = word;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    boolean[][] visited = new boolean[h][w];
                    visited[i][j] = true;
                    if (backTracking(visited, i, j, 1)) return true;
                }
            }
        }
        return false;
    }

    private boolean backTracking(boolean[][] visited, int i, int j, int len) {
        if (len == word.length()) return true;
        for (int[] d : dxy) {
            int x = d[0] + i, y = d[1] + j;
            if (x >= 0 && y >= 0 && x < h && y < w &&
                    !visited[x][y] && board[x][y] == word.charAt(len)) {
                visited[x][y] = true;
                if (backTracking(visited, x, y, len + 1)) return true;
                visited[x][y] = false;
            }
        }
        return false;
    }
}
